/**
 * 
 */
package leetCode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.TreeMap;

/**
 * @author zhongfang
 *
 */
public class FindKthSmallestPairDistance {
	class Freq {
		int val;
		int freq;

		@Override
		public int hashCode() {
			return Integer.hashCode(val);
		}

		public void Combine(Freq other) {
			this.freq += other.freq;
		}

	}

	public int smallestDistancePair222(int[] nums, int k) {
		int n = nums.length;
		HashMap<Integer, Integer> map = new HashMap<>(n);// 数值
		for (int i = 0; i < nums.length; i++) {
			map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);// 统计次数
		}
		TreeMap<Integer, Integer> treeMap = new TreeMap<>();// 距离
		return 0;
	}

	/**
	 * 二分查找得目标距离，条件是<=该距离的个数为k，若个数>k,距离--，否则，距离++
	 * 
	 * @param nums
	 * @param k
	 * @return
	 */
	public int smallestDistancePair(int[] nums, int k) {
		Arrays.sort(nums);
		int n = nums.length;
		int low = Integer.MAX_VALUE;
		int high = nums[n - 1] - nums[0];// 最小差和最大差
		for (int i = 1; i < nums.length; i++) {
			low = Math.min(nums[i] - nums[i - 1], low);
		}
		while (low < high) {// 目标距离值
			int mid = (high + low) >> 1;
			int count = findCountLessThan(mid, nums);
			if (count < k) {// 个数小
				low = mid + 1;
			} else {
				high = mid;
			}
		}
		return 0;
	}

	private int findCountLessThan(int mid, int[] nums) {
		int count = 0;
		for (int i = 0; i < nums.length; i++) {
			int j = i + 1;
			while (j < nums.length && nums[j] - nums[i] <= mid) {
				j++;
			}
			count += (j - i - 1);
		}
		return count;
	}

	/**
	 * @param args
	 */
	public static void main(String[] aStrings) {
		HashMap<Integer, Integer> map = new HashMap<>();
		int[] nums = { 1, 1, 3 };
		int k = 1;
		System.out.println(new FindKthSmallestPairDistance().smallestDistancePair(nums, k));
	}

}
